/**
 * 带权结点构造函数
 * @param {*} data 结点值
 * @param {Number} weight 结点权值
 * @param {TreeNodeWithWeight} left 左孩子
 * @param {TreeNodeWithWeight} right 右孩子
 */
function TreeNodeWithWeight(data, weight, left, right) {
	this.data = data;
	this.weight = weight;
	this.left = left;
	this.right = right;
}

/**
 * 赫夫曼树构造函数
 * @param {Array<TreeNodeWithWeight>} nodes 传入一个带权结点的集合用于构造赫夫曼树
 */
function HuffmanTree(nodes) {
	while (nodes.length > 1) {
		// 找出权重最小结点
		let minium = nodes[0];
		let miniumIndex = 0;
		for (let i = 1; i < nodes.length; i++) {
			if (nodes[i].weight < minium.weight) {
				minium = nodes[i];
				miniumIndex = i;
			}
		}
		// 从列表中移除权重最小结点
		nodes.splice(miniumIndex, 1);
		// 再找权重第二小的结点
		let penultimate = nodes[0];
		let penultimateIndex = 0;
		for (let i = 1; i < nodes.length; i++) {
			if (nodes[i].weight < penultimate.weight) {
				penultimate = nodes[i];
				penultimateIndex = i;
			}
		}
		// 从列表移除第二小的结点
		nodes.splice(penultimateIndex, 1);
		// 两者左右孩子构成一个二叉树
		let newTreeRoot = new TreeNodeWithWeight(null, minium.weight + penultimate.weight, minium, penultimate);
		// 新二叉树根结点加入结点集合
		nodes.push(newTreeRoot);
	}
	// 最后，集合中只有一个结点就是赫夫曼树的根结点
	this.root = nodes[0];
}

// 测试

/**
 * 先序遍历二叉树
 * @param {TreeNodeWithWeight} root 二叉树根结点
 * @param {Array<TreeNodeWithWeight>} result 用于存放结果的集合
 */
function preorderTraverse(root, result) {
	if (root != null) {
		result.push(root);
		preorderTraverse(root.left, result);
		preorderTraverse(root.right, result);
	}
}

/**
 * 中序遍历二叉树
 * @param {TreeNodeWithWeight} root 二叉树根结点
 * @param {Array<TreeNodeWithWeight>} result 用于存放结果的集合
 */
function inorderTraverse(root, result) {
	if (root != null) {
		inorderTraverse(root.left, result);
		result.push(root);
		inorderTraverse(root.right, result);
	}
}

// 构造一个赫夫曼树
let node1 = new TreeNodeWithWeight('a', 7, null, null);
let node2 = new TreeNodeWithWeight('b', 5, null, null);
let node3 = new TreeNodeWithWeight('c', 2, null, null);
let node4 = new TreeNodeWithWeight('d', 4, null, null);
let nodes = new Array(node1, node2, node3, node4);
let tree = new HuffmanTree(nodes);
// 遍历试一下
let result = new Array();
preorderTraverse(tree.root, result);
let resultStr = '先序遍历：';
for (let node of result) {
	resultStr = resultStr + node.data + ':' + node.weight + ' ';
}
console.log(resultStr);
result = new Array();
inorderTraverse(tree.root, result);
resultStr = '中序遍历：';
for (let node of result) {
	resultStr = resultStr + node.data + ':' + node.weight + ' ';
}
console.log(resultStr);